package main

import "fmt"

// 如何判断一个数组是否是二元查找树后序遍历的序列

func main() {
	data := []int{1, 3, 2, 5, 7, 6, 4}
	fmt.Println(isPostorder(data, 0, len(data)-1))
}

func isPostorder(arr []int, start int, end int) bool {
	if arr == nil {
		return false
	}

	root := arr[end]

	var i, j int

	// 寻找左子树和右子树的分界点
	for i = start; i < end; i++ {
		if arr[i] > root {
			break
		}
	}

	// 右子树的值应该都大于根节点的值
	for j = i; j < end; j++ {
		if arr[j] < root {
			return false
		}
	}

	leftIsPostorder := true
	rightIsPostorder := true

	if i > start {
		leftIsPostorder = isPostorder(arr, start, i-1)
	}
	if i < end {
		rightIsPostorder = isPostorder(arr, i, end-1)
	}
	return leftIsPostorder && rightIsPostorder
}
